Long Term Evolution (LTE) system is a modern mobile communication standard designed to provide seamless internet protocol (IP) connectivity between user equipment (UE) and a package data network (PDN). LTE system uses Hybrid Automatic Repeat Request (HARQ) in an effort to guarantee transmission reliability and to increase channel throughput. HARQ is a stop-and-wait scheme, where subsequent transmission can take place only after receiving ACK/NACK from the receiving entity. At the receiver side, the received information is stored temporarily on HARQ memory. If the received message is not decoded correctly, the valuable stored information can be combined with subsequent information of the same message to correctly decode the message. With the ever-increasing data rates in the mobile network, the amount of data to be stored in an receiving HARQ queue increases dramatically. For example, a category-four HARQ requires approximately 11 mega bits of external memory and 1.4 mega bits of internal memory for storing one HARQ copy. To mitigate the demand for increasing HARQ memory size, data compression at the receiving HARQ queue is needed.
Vector Quantization (VQ) is an efficient data compression method based on the principal of block coding. A VQ maps k-dimensional vectors in the vector space into a finite set of vector called a codeword. The set of all the codeword is a codebook. The VQ takes a source data vector and associates it with a codeword that is the nearest neighbor. When using VQ to compress the HARQ data, some special feature of the HARQ data should be considered. HARQ is a powerful combination of forward error correction (FEC), error detection and retransmission scheme. To maximize the performance of the error correction coding, posterior probabilities of the bits that were transmitted need to be stored while waiting for the next retransmission, usually in the form of log-likelihood ratio (LLR). One of the common compression scheme is Maximum Mutual Information (MMI) based VQ for LLR. The criterion is to maximize the mutual information between the original bits and the quantized LLR.
There are two issues associated with the VQ design for HARQ data. The first is how to generate a codebook efficiently. The second is how to optimize an MMI scheme for VQ. In a simple VQ design, a code vector is partitioned into a codeword in a codebook. Instead of storing the code vector itself, an index to the code vector is stored. Upon decompressing, the index is used to retrieve the codeword which is a close proximate to the code vector. A simple VQ method requires an exhaustive search of the codebook for each data vector. Such process is computationally expensive. A more efficient way is required for real time HARQ VQ design.
One problem is how to generate a codebook efficiently. The classical generalized Lloyd algorithm (GLA) is the most cited and widely used VQ method due to its simplicity and relatively good fidelity. However, it requires much higher processing resource. To apply GLA, a distance is defined in RK, where K>1. GLA consists of two-step iterations. In the first step, the training points are associated with the closest points in the codebook based on selected distance measure, called nearest neighbor condition. In the second step, the centroids of each set of training points are selected as the new reconstruction value, called centroids condition. The algorithm can start with an initial codebook provided by other algorithm, or simply taken randomly from the training set. To calculate the distance, GLA usually is applied in conjunction with Euclidean distance, which results in minimization of the mean squared error (MSE). It is also easily applicable to use other distance measure for GLA, such as the MMI approach. In either classical GLA or some proposed modified Lloyd algorithm, problems exist for not being efficient in codebook generation or require extra buffer/memory space for implementation.
Another problem is how to optimize an MMI scheme for VQ. The limitation of traditional VQ algorithm demands high processing power and memory space. Assume a random vector l={l1, . . . , lk}. To design an optimal codebook, we draw nτ samples of l as training points, which we can model with a random vector, t={t1, . . . , tK}, with values in an alphabet Γ={1, . . . , N}, where N is the number of cells of the VQ. For HARQ with LLR, assume xk is the original bit and yk is the reconstruction value for its LLR. I(.;.) is the mutual information between random variables, H(.) is the entropy and H(.|.) is the conditional entropy of a random variable given that another is observed. To maximize the mutual information between the original bits and the quantized LLR, the VQ needs to ensure minimize the mutual information loss ΔI=H(Xk|Yk)−H(Xk|Lk). Further, the probability that an input point falls in region Ri is defined as: p(i)=ni/nΓ, where ni=|{tεRi}|, which is the probability of a given quantizer out is approximated by the relative number of training points that fall in the region associated with the output value i. The posterior p(xk|i), which is the average posterior probability for the original bit conditioned on the training points belonging to Ri, can be obtained by: p(xk|i)=(ni/nΓ) ΣlεRip(xk|yk). The quantized version of LLR can be represented by the index associated with the vector quantizer output and the conditional entropy satisfies: H(Xk|Il)=−Σxkε{0,1}Σi=1Np(xk|i)log2 p(xk|i). The final expression for mutual information loss ΔI=(1/nΓ)ΣtεΓDKL(pxk|t∥qxk|t), where DKL(p∥q) is the KL divergence between probability distributions p and q, defined on random variables which share the same alphabet. Applying this algorithm to implement a MMI VQ requires large extra buffer space and may introduce big distortion. It is not an efficient codebook design. An optimized VQ algorithm is disclosed in this invention to make the codebook design more efficient.